package leetcode.D800.T710;

import java.util.*;

class Solution {

//    private Map<Integer, Integer> map = new HashMap<>();
//    private Random random = new Random();
//    private int whiteLen;
//
//    public Solution(int N, int[] blacklist) {
//        whiteLen = N - blacklist.length;
//        Set<Integer> set = new HashSet<>();
//        for(int i=0; i<blacklist.length; ++i) {
//            if(blacklist[i] >= whiteLen) {
//                set.add(blacklist[i]);
//            }
//        }
//        int last = N - 1;
//        for(int i=0; i<blacklist.length; ++i) {
//            if(blacklist[i] < whiteLen) {
//                while(set.contains(last)) {
//                    --last;
//                }
//                map.put(blacklist[i], last--);
//            }
//        }
//    }
//
//    public int pick() {
//        int key = random.nextInt(whiteLen);
//        return map.getOrDefault(key, key);
//    }

    private Map<Integer, Integer> map;
    private Random random;
    private int writeLen;

    // 二刷
    public Solution(int n, int[] blacklist) {
        writeLen = n - blacklist.length;
        map = new HashMap<>();
        random = new Random();
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<blacklist.length; ++i) {
            if(blacklist[i] >= writeLen) {
                set.add(blacklist[i]);
            }
        }
        int last = n - 1;
        for(int i=0; i<blacklist.length; ++i) {
            if(blacklist[i] < writeLen) {
                while(set.contains(last)) {
                    --last;
                }
                map.put(blacklist[i], last--);
            }
        }
    }

    public int pick() {
        int result = random.nextInt(writeLen);
        return map.getOrDefault(result, result);
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(N, blacklist);
 * int param_1 = obj.pick();
 */